// 给定一个二叉搜索树的根节点root，以及一个值key
// 要求从二叉搜索树中删除key对应的节点，并保证删除后的树仍是二叉搜索树，
// 要求算法时间复杂度为O(h),h为树的高度，最后返回二叉搜索树的根节点
function deleteNode(root, key) {
    if (!root) {
        return root
    }
    if (root.val < key) {
        root.right = deleteNode(root.right, key)
    } else if (root.val > key) {
        root.left = deleteNode(root.left, key)
    } else {
        if (!root.left && !root.right) {
            return null
        } else if (!root.left) {
            return root.right
        } else if (!root.right) {
            return root.left
        } else {
            // 找右子树最左侧的叶子节点
            let cur = root.right
            while (cur.left) {
                cur = cur.left
            }
            cur.left = root.left
            return root.right
        }
    }
    return root
}

const root = {
    val: 4,
    left: {
        val: 3,
        left: {
            val: 2,
        },
        right: {
            val: 3.5,
            left: {
                val: 3.1
            }
        },
    },
    right: {
        val: 6,
    },
};

console.log(deleteNode(root, 2))

// 思路，迭代法
function deleteOneNode(target) {
    if (!target) {
        return target
    }
    if (!target.left) {
        return target.right
    }
    if (!target.right) {
        return target.left
    }
    let cur = target.right
    while (cur.left) {
        cur = cur.left
    }
    cur.left = target.left
    return target.right
}
function deleteNode2(root, key) {
    if (!root) {
        return root
    }
    let cur = root
    let pre
    while (cur) {
        if (cur.val > key) {
            pre = cur
            cur = cur.left
        } else if (cur.val < key) {
            pre = cur
            cur = cur.right
        } else {
            if (!pre) {
                return deleteOneNode(cur)
            } else {
                if (pre.left === cur) {
                    pre.left = deleteOneNode(cur)
                }
                if (pre.right === cur) {
                    pre.right = deleteOneNode(cur)
                }
            }
            return root
        }
    }
    return root
}

const root2 = {
    val: 4,
    left: {
        val: 3,
        left: {
            val: 2,
        },
        right: {
            val: 3.5,
            left: {
                val: 3.1
            }
        },
    },
    right: {
        val: 6,
    },
};

console.log(deleteNode2(root2, 2))